package com.zzg.datastructure.search;

import java.util.Arrays;

/**
 * @Author zhengzg
 * @Date 2022-09-15
 * @Version v1.0
 *
 * 斐波那契数列查找方法：要求数组有序
 */
public class FibonacciSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 100, 1234};

        fibSearch(arr,89);

    }

    /**
     * 创建斐波那契数列
     * @return 斐波那契数列
     */
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        return f;
    }

    public static int fibSearch(int[] a,int key) {
        int low = 0;
        int height = a.length - 1;
        // 表示斐波那契分割数值的下标
        int k = 0;
        int mid = 0;
        int[] f = fib();
        // 获取斐波那契分割数值的下标
        while (height > f[k] - 1) {
            k++;
        }
        // 因为f[k]的值可能大于a的长度，因此需要构建一个新的数组
        int[] temp = Arrays.copyOf(a,f[k]);
        // 将temp多的部分填充，一般用原数组的最大值
        for (int i = height; i < temp.length; i++) {
            temp[i] = a[height];
        }

        // 符合长度范围可以继续寻找
        while (low <= height) {
            /*
             * F(k)-1 = F(k-1)-1 + F(k-2)-1 + 1
             * mid 为位于黄金分割点附近的值
             * F(k-1) - 1 + low = mid 开头的值加上前半部分数据的总数等于mid，接近黄金分割点
             */
            mid = low + f[k-1] - 1;
            if (key < temp[mid]) {
                height = mid - 1;
                // k--是因为查询的值小于mid位置的值，证明要向小的值方向查找
                // f(k-1) 可以继续拆分 f(k-2) + f(k-3)
                // 而此时的黄金分割点附近应该是，low + f(k-2)
                // 所以此时k--
                k--;
            } else if (key > temp[mid]) {
                // k-2是因为查询的值大于mid位置的值，证明要向打的值方向查找
                // f(k) = f(k-1) + f(k-2)
                // f(k-2)是大的方向，那么此时应该拆分f(k-2)
                // f(k-2) = f(k-3) + f(k-4),那么此时黄金分割点附近应该是 low + f(k-3)
                // 此时k-2
                low = mid + 1;
                k -= 2;
            } else {
                //找到，需要确定返回的是那个下标
                // 因为mid取得是黄金分割点附近，可能出现大于height的情况，所以在大于时选择height
                return Math.min(mid, height);
            }
        }
        return -1;
    }
}
